Linear programming (LP) decoding for low-density parity-check (LDPC) codesproposed by Feldman et al. is shown to have theoretical guarantees in severalregimes and empirically is not observed to suffer from an error floor. Howeverat low signal-to-noise ratios (SNRs), LP decoding is observed to have worseerror performance than belief propagation (BP) decoding. In this paper, we seekto improve LP decoding at low SNRs while still achieving good high SNRperformance. We first present a new decoding framework obtained by trying tosolve a non-convex optimization problem using the alternating direction methodof multipliers (ADMM). This non-convex problem is constructed by adding apenalty term to the LP decoding objective. The goal of the penalty term is tomake "pseudocodewords", which are the non-integer vertices of the LP relaxationto which the LP decoder fails, more costly. We name this decoder class the"ADMM penalized decoder". In our simulation results, the ADMM penalized decoderwith $\ell_1$ and $\ell_2$ penalties outperforms both BP and LP decoding at allSNRs. For high SNR regimes where it is infeasible to simulate, we use aninstanton analysis and show that the ADMM penalized decoder has better high SNRperformance than BP decoding. We also develop a reweighted LP decoder usinglinear approximations to the objective with an $\ell_1$ penalty. We show thatthis decoder has an improved theoretical recovery threshold compared to LPdecoding. In addition, we show that the empirical gain of the reweighted LPdecoder is significant at low SNRs.
展开▼
